package 中等.其他;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个整数数组和一个整数 k，你需要在数组里找到 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。
 * 这里将 k-diff 数对定义为一个整数对 (nums[i], nums[j])，并满足下述全部条件：
 * 0 <= i < j < nums.length
 * |nums[i] - nums[j]| == k
 * 注意，|val| 表示 val 的绝对值。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/k-diff-pairs-in-an-array
 */
public class 数组中的kdiff数对_532 {

    public static void main(String[] args) {

        int[] nums = {1, 3, 1, 5, 4};
        System.out.println(findPairs(nums, 0));

    }

    /**
     * 哈希表
     * 因为 (1,3) 和 (3,1) 是同一个，且 k 是确定的，
     * 那么存入一个最小值，就已经确定了整个数对
     *
     * @param nums
     * @param k
     * @return
     */
    public static int findPairs(int[] nums, int k) {
        Set<Integer> records = new HashSet<>();
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            if (numSet.contains(num + k)) {
                records.add(num);
            }
            if (numSet.contains(num - k)) {
                records.add(num - k);
            }
            numSet.add(num);
        }
        return records.size();
    }

    /**
     * 排序+指针
     * 因为 (1,3) 和 (3,1) 是同一个数对，索引和数字的对应关系就无关紧要了
     * 先排序好数组，用指针查找
     *
     * @param nums
     * @param k
     * @return
     */
//    public static int findPairs2(int[] nums, int k) {
//        Arrays.sort(nums);
//        Set<Integer> records = new HashSet<>();
//        int left = 0, right = 0;
//        while (right < nums.length) {
//            while (right < nums.length && nums[right] - nums[left] < k) right++;
//            if (right < nums.length && nums[right] - nums[left] == k) records.add(nums[left]);
//            left++;
//        }
//        return records.size();
//    }

}
